/**	Code for range coding, derived from public domain work by Dmitry Subbotin

Authors:	Dmitry Subbotin (initial author of the Carry-less Range Coder)
			Wei Li (D language) <oldrev@gmail.com>
License:	BSD

Reference:	http://sachingarg.com/compression/entropy_coding/64bit/
*/

module dotmars.compression.algorithm.rangecoding;

import dotmars.base.stdtypes;
import dotmars.io.stream;


template RangeCodingBase()
{
	const uint Top = 1 << 24;
	const uint Bottom = 1 << 16;
	uint m_low = 0;
	uint m_range = uint.max;
}

struct RangeEncoding(M)
{
	public alias RangeEncoding!(M) SelfType;
	public alias M Model;

	mixin RangeCodingBase;

	private Model m_model;
	private bool m_flushed = false;
	private Sink!(ubyte) m_sink = null;

	void init(Sink!(ubyte) sink)
	{
		assert(sink !is null);
		m_sink = sink;
		m_model.init();
	}

	void encodeRange(uint symbolLow, uint symbolHigh, uint totalRange)
	{
		m_range /= totalRange;
		m_low += symbolLow * m_range;
		m_range *= symbolHigh - symbolLow;

		while ((m_low ^ (m_low + m_range)) < Top || m_range < Bottom && ((m_range = -m_low & (Bottom - 1)), true))
		{
			ubyte b = m_low >> (m_low.sizeof * 8 - 8);
			m_sink(b);
			m_range <<= 8;
			m_low <<= 8;
		}
	}

	void encode(uint symbol)
	{
		encodeRange(m_model.low(symbol), m_model.high(symbol), m_model.total);
		m_model.update(symbol);
	}

	void flush()
	{
		if(!m_flushed)
		{
			for(size_t i = 0; i < m_low.sizeof; i++)
			{
				ubyte b = m_low >> (m_low.sizeof * 8 - 8);
				m_sink(b);
				m_low <<= 8;
			}
			m_flushed = true;
		}
	}
}

struct RangeDecoding(M)
{
	public alias RangeDecoding!(M) SelfType;
	public alias M Model;

	mixin RangeCodingBase;

	private Model m_model;
	private uint m_code;
	private Emitter!(ubyte) m_emitter;

	void init(Emitter!(ubyte) emitter)
	{
		assert(emitter !is null);
		m_emitter = emitter;
		for(size_t i = 0; i < m_code.sizeof; i++)
		{
			m_code = (m_code << 8) | emitter();
		}
		m_model.init();
	}

	uint currentCount(uint totalRange) //积累频率
	{
		return (m_code - m_low) / (m_range /= totalRange);
	}

	void decodeRange(uint symbolLow, uint symbolHigh, uint totalRange)
	{
		m_low += symbolLow * m_range;
		m_range *= symbolHigh - symbolLow;

		while ((m_low ^ m_low + m_range) < Top || m_range < Bottom && ((m_range = -m_low & Bottom - 1), true))
		{
			m_code= m_code << 8 | m_emitter(), m_range <<= 8, m_low <<= 8;
		}

	}

	uint decode()
	{
		uint count = currentCount(m_model.total);
		uint sym = m_model.getSymbol(count);
		decodeRange(m_model.low(sym), m_model.high(sym), m_model.total);
		m_model.update(sym);
		return sym;
	}
}

//简单0阶模型
struct OrderZeroModel(uint MaxSym, uint MaxScl = 16383)
{
	public const uint MaxSymbol = MaxSym;
	public const uint MaxScale = MaxScl;


	static if(MaxScale > 0xffff)
		private uint[MaxSymbol + 2] m_freq;
	else
		private ushort[MaxSymbol + 2] m_freq;


	void init()
	{	
		for(size_t i = 0; i < m_freq.length; i++) 
		{
			m_freq[i] = i;
		}
	}

	private void rescale()
	{
		for(uint i = 1; i < m_freq.length; i++) 
		{
			m_freq[i] /= 2;
			if(m_freq[i] <= m_freq[i - 1]) 
				m_freq[i] = m_freq[ i - 1] + 1;
		}
	}

	void update(uint sym)
	{
		for(size_t i = sym + 1; i < m_freq.length; i++) {
			m_freq[i]++;
		}

		if(total() >= MaxScale) 
			rescale();
	}

	uint getSymbol(uint n)
	{
		uint sym = MaxSymbol;
		while(m_freq[sym] > n) --sym;

		return sym;
	}

	uint total()
	{
		return m_freq[m_freq.length - 1];
	}

	uint low(uint sym)
	{
		return m_freq[sym];
	}

	uint high(uint sym)
	{
		return m_freq[sym + 1];
	}

	uint opIndex(uint rhs)
	{
		return m_freq[rhs];
	}
}

